package com.zhugang.week13.stack;

import java.util.Stack;

/**
 * @program algorithms
 * @description: isValid
 * @author: chanzhugang
 * @create: 2022/09/12 22:51
 */
public class IsValid {

    /**
     * 20 有效的括号
     * https://leetcode.cn/problems/valid-parentheses/
     * 连连消问题：栈里存储都是没有消掉的数据
     *
     * @param s
     * @return
     */
    public boolean isValid1(String s) {
        // 逆向思维：栈存的是对应右括号的字符
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }


    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                // 左括号压入栈
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    // 没有押入左括号
                    return false;
                }
                char popC = stack.pop();
                if (c == ')' && popC != '(') {
                    return false;
                }
                if (c == ']' && popC != '[') {
                    return false;
                }
                if (c == '}' && popC != '{') {
                    return false;
                }
            }
        }
        // 栈为null，括号全消了
        return stack.isEmpty();
    }

}